package leetcode.method.dynamic_programming;

/**
 * 乘法太多浪费计算时间
 */
public class Program188BuyAndSellTicket {

    public Program188BuyAndSellTicket() {
    }

    public int maxProfit(int k, int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int[][]  trance = new int[k][2];
        for (int i =0; i < k; i++) {
            trance[i][0] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0; j < k; j++) {
                // 买
                if (j == 0) {
                    trance[j][0] = Math.max(trance[j][0], -prices[i]);
                } else {
                    trance[j][0] = Math.max(trance[j][0], trance[j - 1][1] - prices[i]);
                }
                // 卖
                trance[j][1] = Math.max(trance[j][1], trance[j][0] + prices[i]);
            }
        }

        return trance[k - 1][1];
    }

    public static void main(String[] args) {
        Program188BuyAndSellTicket myStack = new Program188BuyAndSellTicket();
//        int[] prices = {2,4,1};
//        System.out.println(myStack.maxProfit(2, prices));
        int[] prices1 = {3,2,6,5,0,3};
        System.out.println(myStack.maxProfit(2, prices1));
    }
}
